package day_7_12;

import java.util.Deque;
import java.util.LinkedList;

public class Main3 {
    /**
     * 739. 每日温度
     * https://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked
     */
    public int[] dailyTemperatures2(int[] temperatures) {
        // 从右往左，进行遍历数组
        int n = temperatures.length;
        int[] ret = new int[n];
        Deque<Integer> deque = new LinkedList<>();
        for(int i = n - 1;i >= 0;i--) {
            int t = temperatures[i];
            while(!deque.isEmpty() && t >= temperatures[deque.peek()]) {
                deque.pop();
            }

            if(!deque.isEmpty()) {
                // 说明当前t是小于栈顶数据的，那么对于t来说，栈顶这个数据就是第一次的升温值
                ret[i] = deque.peek() - i;
            }
            // 将数据进行放入栈中
            deque.push(i);
        }
        return ret;
    }

    public int[] dailyTemperatures1(int[] temperatures) {
        // 从左往右，进行遍历数组
        int n = temperatures.length;
        int[] ret = new int[n];
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0;i < n;i++) {
            int t = temperatures[i];
            while(!deque.isEmpty() && t > temperatures[deque.peek()]) {
                // 说明出现第一个使 栈顶位置数据升温的情况
                int j = deque.pop();
                ret[j] = i - j;
            }
            // 将数据进行放入栈中
            deque.push(i);
        }
        return ret;
    }
}
